package com.wzh.test.graphic;

import java.util.*;

public class Graphic {
    public ArrayList<String> vertexList;

    //存储对应的邻接矩阵
    public Integer[][] edges;

    //表示边的数目
    public int numOfEdges;

    private Set<Integer> visitedIndex;

    /**
     * @param n 有几个顶点
     */
    public Graphic(int n) {
        vertexList = new ArrayList<String>(n);
        edges = new Integer[n][n];
        numOfEdges = 0;
    }

    public Graphic(int n,int defaultWeight){
        vertexList = new ArrayList<String>(n);
        edges = new Integer[n][n];
        numOfEdges = 0;
        for(int i = 0; i < n;i++){
            for(int j = 0; j < n;j++){
                this.edges[i][j] = defaultWeight;
            }
        }
    }

    /**
     * 添加节点
     * @param vertex
     */
    public void addVertex(String vertex) {
        this.vertexList.add(vertex);
    }

    /**
     * 添加连接线
     * @param vertex1
     * @param vertex2
     * @param weight
     */
    public void addEdge(String vertex1, String vertex2, int weight) {

        int index1 = this.vertexList.indexOf(vertex1);
        int index2 = this.vertexList.indexOf(vertex2);
        this.edges[index1][index2] = weight;
        this.edges[index2][index1] = weight;
        this.numOfEdges++;

    }

    public void showGraphic() {
        for (int i = 0; i < this.edges.length; i++) {
            System.out.println(Arrays.toString(this.edges[i]));
        }
    }

    public int getNumOfEdges() {
        return numOfEdges;
    }

    /**
     * 返回节点i对应的数据
     */
    public String getValueByIndex(int index){
        return this.vertexList.get(index);
    }

    public int getWeight(String v1,String v2){
        int index1 = this.vertexList.indexOf(v1);
        int index2 = this.vertexList.indexOf(v2);
        return this.edges[index1][index2];
    }

    public int getFirstNeighbourIndex(int row){
        for(int j = 0; j < this.vertexList.size();j++){
            if(this.edges[row][j] > 0){
                return j;
            }
        }
        return -1;
    }

    public int getNextNeighbourIndex(int row ,int column){
        for(int j = column + 1;j < this.vertexList.size();j++){
            if(this.edges[row][j] > 0){
                return j;
            }
        }
        return -1;
    }

    public void dfs(){
        this.visitedIndex = new HashSet<>();
        for(int i = 0; i < this.vertexList.size();i++){
            if(!this.visitedIndex.contains(i)) {
                dfs(i);
            }
        }
    }

    private void dfs(int i){
        this.visitedIndex.add(i);
        System.out.println(this.vertexList.get(i));
        int neighbourIndex = getFirstNeighbourIndex(i);
        while (neighbourIndex != -1){
            if(!this.visitedIndex.contains(neighbourIndex)){
                dfs(neighbourIndex);
            }
            neighbourIndex = getNextNeighbourIndex(i,neighbourIndex);
        }
    }

    public void bfs(){
        this.visitedIndex = new HashSet<>();
        for(int i = 0; i < this.vertexList.size();i++) {
            if(!this.visitedIndex.contains(i)) {
                this.bfs(i);
            }
        }
    }

    public void bfs(int i){
        LinkedList<Integer> queue = new LinkedList<>();
        queue.addLast(i);

        this.visitedIndex.add(i);
        System.out.println(this.vertexList.get(i));

        while (queue.size() > 0){
            int u = queue.removeFirst();
            int neighbourIndex = getFirstNeighbourIndex(u);

            while (neighbourIndex > -1){

                if(!this.visitedIndex.contains(neighbourIndex)){
                    queue.addLast(neighbourIndex);
                    this.visitedIndex.add(neighbourIndex);
                    System.out.println(this.vertexList.get(neighbourIndex));
                }
                neighbourIndex = getNextNeighbourIndex(u,neighbourIndex);
            }
        }

    }


}
